package com.banmao.algorithm.No701To900.No707;

public class MyLinkedList {

    LinkedNode dummy_head;
    int size;
    LinkedNode dummy_tail;

    public MyLinkedList() {
        dummy_head = new LinkedNode(-1);
        size = 0;
        dummy_tail = new LinkedNode(-1);
    }

    public int get(int index) {
        if(size < index) {
            return -1;
        }

        LinkedNode cur = dummy_head.next;
        int tempIndex = 0;
        while (cur != null) {
            if(tempIndex == index) {
                // 找到了
                return cur.val;
            }
            cur = cur.next;
            tempIndex++;
        }

        return -1;
    }

    public void addAtHead(int val) {
        if(dummy_head.next == null) {
            // 没有头节点
            LinkedNode newNode = new LinkedNode(val);
            dummy_head.next = newNode;
            dummy_tail.next = newNode;
            size++;
            return;
        }

        // 有头节点
        LinkedNode newNode = new LinkedNode(val, dummy_head.next);
        dummy_head.next = newNode;
        size++;

    }

    public void addAtTail(int val) {
        if(dummy_tail.next == null) {
            // 没有尾节点 == 没有头节点
            LinkedNode newNode = new LinkedNode(val);
            dummy_head.next = newNode;
            dummy_tail.next = newNode;
            size++;
            return;
        }

        // 有尾节点
        LinkedNode newNode = new LinkedNode(val);
        dummy_tail.next.next = newNode;
        dummy_tail.next = newNode;
        size++;

    }

    public void addAtIndex(int index, int val) {
        if(index == this.size) {
            // 加在尾节点后
            addAtTail(val);
        } else if(index <= 0) {
            addAtHead(val);
        } else if(index < this.size) {
            LinkedNode cur = dummy_head.next;
            LinkedNode pre = dummy_head;
            int tempIndex = 0;
            while (cur != null) {
                if(tempIndex == index) {
                    LinkedNode newNode = new LinkedNode(val, cur);
                    pre.next = newNode;
                    this.size++;
                    return;
                }
                tempIndex++;
                pre = cur;
                cur = cur.next;
            }
        }


    }

    public void deleteAtIndex(int index) {
        if(index > this.size || index < 0) {
            return;
        }

        int tempIndex = 0;
        LinkedNode cur = dummy_head.next;
        LinkedNode pre = dummy_head;

        while (cur != null) {
            if(tempIndex == index) {
                pre.next = cur.next;
                if(index == this.size - 1) {
                    dummy_tail.next = pre;
                }
                this.size--;
                return;
            }
            tempIndex++;
            pre = cur;
            cur = cur.next;
        }

    }

    public void printLinkedList() {
        LinkedNode cur = dummy_head.next;

        StringBuffer res = new StringBuffer("[");
        while(cur != null) {
            res.append(cur.val).append(", ");
            cur = cur.next;
        }
        res.replace(res.lastIndexOf(", "), res.length() -1, "]");

        System.out.println(res);

    }

}

class LinkedNode {

    int val;
    LinkedNode next;

    public LinkedNode(int val) {
        this.val = val;
        this.next = null;
    }

    public LinkedNode(int val, LinkedNode next) {
        this.val = val;
        this.next = next;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public LinkedNode getNext() {
        return next;
    }

    public void setNext(LinkedNode next) {
        this.next = next;
    }
}
